package Midium;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

// 207. 课程表
// 拓扑排序
/*
 * 题目：
 * 一共有n门课程，用序号0到n-1表示。给定先修课程集合，判断是否可能完成所有课程学习？
 * 思路：
 * (a,b)代表想要学习a课程，必须已经学了b课程  即 b -> a
 * 创建邻接表list，大小为n，每个结点挂着修习了本课程以后，可以修习后面的哪些课程
 * 初始化邻接表时，判定(a,b)中，如果 b 在 a的结点下面挂着的话，说明出现了环，直接返回false，否则 把a挂在b下面
 * 邻接表初始完毕后
 *   每次出队1个，并将其邻接表对应的挂着的结点全部入队【如果set中已经存在这个点，则不入队】
 *   入队的元素同时保存在set中
 *   当队列为空时，如果set.size() == n 则返回true
 * 邻接表遍历结束，还没有返回true，则返回false
 *
 * 关键点：对于没有先修条件的课，我们可以直接认为它已经学过了
 *
 * 总结：思路是错误的，因为这样做，比如[[0,1],[0,2],[1,3],[3,0]]
 * 默认已经学了2，于是可以学0了，但是学0还有一个要求，就是必须得先学3，因此这样的思路是不可取的方案！
 *
 * 正确思路：
 * 搞一个入边数组（我上面的思路相当于只有一个出边）
 * 每次将入边为0的结点加入到结果中,当不存在入边为0的点时（包含环）或者当所有的点已经加入结果，则结束
 * */
class CourseNode {
    int course;
    CourseNode next;

    CourseNode() {

    }

    CourseNode(int course) {
        this.course = course;
        next = null;
    }

}

public class Solution207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        CourseNode[] list = new CourseNode[numCourses];
        for (int i = 0; i < prerequisites.length; i++) {
            // prerequisites[i][0]代表a,prerequisites[i][1]代表b,想要学a得先学b
            // 意味着a的入边为b
            int a = prerequisites[i][0];
            int b = prerequisites[i][1];
            // 如果list[a]为空，则创建结点b放在这里
            // 如果list[a]不为空，则用b创建一个新的结点，并把这个结点挂在list[a]的最后面
            if (list[a] == null) {
                list[a] = new CourseNode(b);
            } else {
                CourseNode courseNode = new CourseNode(b);
                CourseNode index = list[a];
                while (index.next != null) {
                    index = index.next;
                }
                index.next = courseNode;
            }
        }
        Queue queue = new LinkedList();
        Set set = new HashSet(); //记录已经学的课程
        // 首先记录已经可以学的课程，并加入到队列中
        for (int i = 0; i < numCourses; i++) {
            // 寻找入边为0的点
            if(list[i] == null){
                set.add(i);
                queue.offer(i);
            }
        }
        while (!queue.isEmpty()){
            int course = (int) queue.poll();
            // 更新入边数组，将所有course的点全都去掉
            for (int i = 0; i < numCourses; i++) {
                CourseNode node = list[i];
                CourseNode pre = null;
                while (node != null){
                    if(node.course == course){
                        if(node == list[i]){
                            list[i] = node.next;
                        }else {
                            pre.next = node.next;
                        }
                        break;
                    }else {
                        pre = node;
                        node = node.next;
                    }
                }
            }
            // 每次更新入边数组以后，检查有没有新的入边为0的点，如果有的话，则加入队列(已经加入过的则不再加入)
            for (int i = 0; i < numCourses; i++) {
                // 寻找入边为0的点
                if(list[i] == null && !set.contains(i)){
                    set.add(i);
                    queue.offer(i);
                }
            }
        }
        if(set.size() == numCourses)
            return true;
        return false;
    }


    public boolean canFinish_error(int numCourses, int[][] prerequisites) {
        // 特殊情况：如果没有先修条件，则直接返回true
        if (prerequisites.length == 0)
            return true;
        CourseNode[] list = new CourseNode[numCourses];
        boolean[] jyoukenn = new boolean[numCourses];
        // 开始初始化邻接表，同时记录没有先修条件的课程（true代表有先修条件）
        for (int i = 0; i < prerequisites.length; i++) {
            // prerequisites[i][0]代表a,prerequisites[i][1]代表b,想要学a得先学b
            int b = prerequisites[i][1];
            int a = prerequisites[i][0];
            // 只要a出现，代表a课程是有先修条件的
            jyoukenn[a] = true;
            // 如果 b 在 a的结点下面挂着的话，说明出现了环，直接返回false，否则 把a挂在b下面
            CourseNode x = list[a];
            while (x != null) {
                if (x.course == b) {
                    return false;
                }
                x = x.next;
            }
            // 如果list[b]为空，则创建结点a放在这里
            // 如果list[b]不为空，则用a创建一个新的结点，并把这个结点挂在CourseNode[b]的最后面
            if (list[b] == null) {
                list[b] = new CourseNode(a);
            } else {
                CourseNode courseNode = new CourseNode(a);
                CourseNode index = list[b];
                while (index.next != null) {
                    index = index.next;
                }
                index.next = courseNode;
            }
        }
        // set代表已经学过的课程，首先需要把没有先修条件的课程放进去,因为这些没有先修的课程可能有后续课程，因此也应该放在队列里
        Set set = new HashSet();
        Queue queue = new LinkedList();
        for (int i = 0; i < numCourses; i++) {
            if (jyoukenn[i] == false) {
                set.add(i);
                queue.offer(i);
            }
        }

        // 初始化完毕，根据已经学的课程（默认已经学习了没有先修课程的课），查看是否能学完所有课

        while (!queue.isEmpty()) {
            // 每次取出一个点r，并将list[r]挂着的所有结点全部入队【set中已经存在此点，则不入队】
            int course = (int) queue.poll();
            CourseNode index = list[course];
            while (index != null) {
                if (!set.contains(index.course)) {
                    set.add(index.course);
                    queue.offer(index.course);
                }
                index = index.next;
            }
        }
        if (set.size() == numCourses)
            return true;
        return false;
    }

    public static void main(String[] args) {
//        new Solution207().canFinish(5,new int[][]{{1,4},{2,4},{3,1},{3,2}});
        new Solution207().canFinish(5,new int[][]{{0,1}});
    }
}
